Inhaltlich waren wir letzte Woche stehen geblieben bei kürzesten Wegen.

Wir hatten letzte Woche minimal aufspannende Bäume gemacht, haben da im übrigen ja grundgenom zwei, drei

verschiedene Algorithmen kennengelernt, wobei sie im Kern sehr ähnlich sind, die alle nach diesem sogenannten

Greedy-Prinzip basieren, auf das zurückgehen und am Schluss unterschiedliche Aussehen, aber letztendlich

dasselbe leisten. Wir haben auch gesehen, dass dieser geht zurück auf Kruskal und Prim, dass der Prim-Algorithmus

zumindest für vollständige Grafen auch in dem Sinn bestmöglich ist, weil er ein N²-Laufzeit hat und man ja schließlich

jede Kante mindestens einmal angucken muss für einen aufspannenden Baum. Von daher im gewissen Sinne auch ein bestmöglicher

Algorithmus wir damit kennengelernt haben. Dann haben wir angefangen uns mit kürzesten Wege zu beschäftigen,

sozusagen ein zweiter Klassiker, wenn es um Grafen und Algorithmen geht, neben den minimal aufspannenden Bäumen,

sind es die kürzesten Wege mit den unterschiedlichen Anwendungen, sei es im Internet, sei es wo es sehr häufig auftritt,

dass man solche kürzesten Wege-Algorithmen braucht und da haben wir angefangen erstmal so ein paar Kriterien uns zu erarbeiten,

was kürzeste Wege überhaupt erfüllen müssen, bevor wir dann heute auch sozusagen den ersten oder vielleicht

hoffen wir, dass wir zwei Algorithmen heute hinkriegen, nämlich einmal der auf Deichsrad zurückgeht und der auf

Murbellmann und die Beine vom Charakter sehr unterschiedlich sind, das werden wir aber dann im Detail noch angucken.

Das was im Skript noch steht, ist das Verfahren für a-zügliche Deak-Grafen, das überspringen wir bzw. das machen wir ein Stück weit mit in der Übung,

weil das Grundprinzip kommt nachher nochmal und der Spezialfall a-zügliche Deak-Grafen ist eigentlich so selten,

dass man kaum braucht und von den algorithmischen Techniken haben wir zum einen Depth-Furseurs und Bread-Furseurs schon gehabt

und das andere ist das Prinzip von Murbellmann, das werden wir dann heute noch kennenlernen für eine allgemeinere Klasse von Grafen.

Oder für ein D von V nach R sei C ij D, ja wir tun den Label oben dran, weil wir mit dem D viel spielen,

das C ij plus D i minus D i seien die reduzierten Bogengewichte bezüglich D.

Also warum man die jetzt reduzierten Bogengewichte nennt, das wird vielleicht erst später noch klar im zweiten Teil der Vorlesung.

Wenn wir uns um lineare Programmierung kümmern, da wird auch sowas wie reduzierte Kosten auftreten.

Das sind sozusagen, wenn man so möchte, von einem aktuellen Standpunkt aus sozusagen die zusätzlichen Kosten, die mir sozusagen entstehen würden.

Das sind die Originalkosten, die manipuliere ich sozusagen mit den aktuellen Werten, die ich schon in Anführungszeichen mich gekostet habe.

Wenn man die Kostet hat, steht in dem D i minus das, was in dem D auf ist. Also das ist sozusagen, wenn man so möchte, die Marginalkosten, die sozusagen zusätzlich entstehen, wenn ich da drüber laufen würde.

Im allgemeinen Kontext heißen die reduzierten Kosten und wir werden sehen, dass man kürzeste Wege nachher auch in dem 11-linearen Programmierungskontext sehen kann.

Und da werden wir sehen, wenn ich genau an die Stelle erinnere, bei kürzesten Wegen, da sehen die reduzierten Kosten genauso aus.

Also in dem Sinn werden wir da noch ein deutlich allgemeines Konzept kennenlernen.

Aber so ein bisschen Intuition, also tut man sich immer schwer, weil sozusagen, wie diesen reduzierten Kosten häufig nicht eine physikalische Größe dahinter steckt,

aber letztendlich kann man so ein Stück weit alles die Marginalkosten sehen, die es mich kostet, wenn ich von hier, von i, zu dem Knoten j möchte.

Ich sage mal, das D i sagt, was hat mich das gekostet, bis zu dem i zu kommen und hier, das ist das, was es mich gekostet hat, bis zum j zu kommen.

Jetzt sind die neuen Kosten angenommen, ich würde tatsächlich dahin laufen, dann sind meine neuen Kosten bis zum i laufen, plus das hier,

aber dafür muss ich die natürlich wieder abziehen, weil ich jetzt sozusagen auf einem neuen Weg dahin laufe und nicht über den alten.

Also das ist sozusagen der Zusatzauffang, der mir entsteht, wenn ich mich jetzt entscheide, zu dem j über den i zu laufen.

Also der Zusatzauffang, der entsteht, da muss ich natürlich den Aufwand, den ich bislang betrieben habe, abziehen.

Deswegen das Minus D. Und deshalb das reduziert. Oder Marginalgewichte, je nachdem, wie wir haben gesagt.

Man bezeichnet die halt in dem allgemeinen Kontext immer als reduzierte Kosten.

Gut, ein paar Eigenschaften von dieser Größe, das ist die in Proposition 7,7 zusammengefasst.

Wenn ich einen Kreis habe, dann hebt sich das gerade auf, also Summe der ij aus W, Cij, W ist gleich Summe der ij aus W, Cij.

Warum ist das so? Naja, wenn Sie hier irgendwo einen Kreis haben, und hier steht das Cij, wenn hier das i ist, hier ist das j, hier ist das k,

dann steht er hier im Plus Di minus Dj und an der Stelle steht ein Cj Plus Dj minus Dk.

Das heißt hier an der Stelle hebt sich das gerade immer auf.

Und wenn Sie einmal einen Kreis haben, dann heben Sie sich alle auf.

Das heißt der Wert eines Kreises bezüglich der Originalgewichte ist derselbe wie bezüglich der reduzierten Gewichte.

Das ist das, was hier steht. Und die Eigenschaft werden wir später noch ein paar Mal brauchen, auch im Kontext von etwas komplexeren Algorithmen,

wenn es um Minimalpfostenflüsse geht, werden wir das auch noch mal brauchen.

Gut, bei Wegen, also wenn D im Weg ist, naja, was gilt dann? Dann bleibt halt der Anfang und das Ende übrig.

Das heißt, wenn ich die Summe über Cjd und ij im T nehme, dann ist das das gleiche wie bezüglich der Originalgewichte.

Nur der Anfang bleibt mir halt ein Weg von u nach v du minus dv.

Also das ist ähnlich wie hier. Also das ist, es werden alle Zwischenknoten, kommt einmal das Negative, einmal das Positive,